// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// go generate生成的代码；不要编辑。

package suffixarray

func text_64(text []byte, sa []int64) {
	if int(int64(len(text))) != len(text) || len(text) != len(sa) {
		panic("suffixarray: misuse of text_64")
	}
	sais_8_64(text, 256, sa, make([]int64, 2*256))
}

func sais_8_64(text []byte, textMax int, sa, tmp []int64) {
	if len(sa) != len(text) || len(tmp) < int(textMax) {
		panic("suffixarray: misuse of sais_8_64")
	}

	// 琐碎的基本情况。排序0或1件事情很容易。
	if len(text) == 0 {
		return
	}
	if len(text) == 1 {
		sa[0] = 0
		return
	}

	// 建立由文本字符索引的切片
	// 保留字符频率和桶排序偏移量。
	// 如果一个切片只有足够的tmp，
	// 我们将其作为桶偏移量，并在每次需要时重新计算
	// 字符频率。
	var freq, bucket []int64
	if len(tmp) >= 2*textMax {
		freq, bucket = tmp[:textMax], tmp[textMax:2*textMax]
		freq[0] = -1 // 标记为未初始化
	} else {
		freq, bucket = nil, tmp[:textMax]
	}

	// SAIS算法。
	// 每个调用都通过sa进行一次扫描。
	// 有关每个函数在算法中的角色，请参见文档
	// 中的各个函数。
	numLMS := placeLMS_8_64(text, sa, freq, bucket)
	if numLMS <= 1 {
		// 0或1项已排序。什么也不做。
	} else {
		induceSubL_8_64(text, sa, freq, bucket)
		induceSubS_8_64(text, sa, freq, bucket)
		length_8_64(text, sa, numLMS)
		maxID := assignID_8_64(text, sa, numLMS)
		if maxID < numLMS {
			map_64(sa, numLMS)
			recurse_64(sa, tmp, numLMS, maxID)
			unmap_8_64(text, sa, numLMS)
		} else {
			// 如果maxID==numls，则每个LMS子字符串
			// 都是唯一的，因此两个LMS后缀
			// 的相对顺序仅由前面的LMS子字符串决定。
			// 也就是说，LMS后缀排序顺序与
			// （更简单）LMS子字符串排序顺序匹配。
			// 将原始LMS子字符串顺序复制到
			// 后缀数组目标中。
			copy(sa, sa[len(sa)-numLMS:])
		}
		expand_8_64(text, freq, bucket, sa, numLMS)
	}
	induceL_8_64(text, sa, freq, bucket)
	induceS_8_64(text, sa, freq, bucket)

	// 为呼叫者标记我们重写了tmp。
	tmp[0] = -1
}

func sais_32(text []int32, textMax int, sa, tmp []int32) {
	if len(sa) != len(text) || len(tmp) < int(textMax) {
		panic("suffixarray: misuse of sais_32")
	}

	// 琐碎的基本情况。排序0或1件事情很容易。
	if len(text) == 0 {
		return
	}
	if len(text) == 1 {
		sa[0] = 0
		return
	}

	// 建立由文本字符索引的切片
	// 保留字符频率和桶排序偏移量。
	// 如果一个切片只有足够的tmp，
	// 我们将其作为桶偏移量，并在每次需要时重新计算
	// 字符频率。
	var freq, bucket []int32
	if len(tmp) >= 2*textMax {
		freq, bucket = tmp[:textMax], tmp[textMax:2*textMax]
		freq[0] = -1 // 标记为未初始化
	} else {
		freq, bucket = nil, tmp[:textMax]
	}

	// SAIS算法。
	// 每个调用都通过sa进行一次扫描。
	// 请参阅各个函数的文档
	// 了解每个函数在算法中的作用。
	numLMS := placeLMS_32(text, sa, freq, bucket)
	if numLMS <= 1 {
		// 0或1项已排序。什么也不做。
	} else {
		induceSubL_32(text, sa, freq, bucket)
		induceSubS_32(text, sa, freq, bucket)
		length_32(text, sa, numLMS)
		maxID := assignID_32(text, sa, numLMS)
		if maxID < numLMS {
			map_32(sa, numLMS)
			recurse_32(sa, tmp, numLMS, maxID)
			unmap_32(text, sa, numLMS)
		} else {
			// 如果maxID==numls，则每个LMS子字符串
			// 是唯一的，因此两个LMS后缀
			// 的相对顺序仅由前面的LMS子字符串确定。
			// 也就是说，LMS后缀排序顺序与
			// （更简单的）LMS子字符串排序顺序匹配。
			// 将原始LMS子字符串顺序复制到
			// 后缀数组目标中。
			copy(sa, sa[len(sa)-numLMS:])
		}
		expand_32(text, freq, bucket, sa, numLMS)
	}
	induceL_32(text, sa, freq, bucket)
	induceS_32(text, sa, freq, bucket)

	// 为呼叫者标记我们重写了tmp。
	tmp[0] = -1
}

func sais_64(text []int64, textMax int, sa, tmp []int64) {
	if len(sa) != len(text) || len(tmp) < int(textMax) {
		panic("suffixarray: misuse of sais_64")
	}

	// 琐碎的基本情况。排序0或1件事情很容易。
	if len(text) == 0 {
		return
	}
	if len(text) == 1 {
		sa[0] = 0
		return
	}

	// 建立由文本字符索引的切片
	// 保留字符频率和桶排序偏移量。
	// 如果一个切片只有足够的tmp，
	// 我们将其作为桶偏移量，并在每次需要时重新计算
	// 字符频率。
	var freq, bucket []int64
	if len(tmp) >= 2*textMax {
		freq, bucket = tmp[:textMax], tmp[textMax:2*textMax]
		freq[0] = -1 // 标记为未初始化
	} else {
		freq, bucket = nil, tmp[:textMax]
	}

	// SAIS算法。
	// 这些调用中的每一个都通过sa进行一次扫描。
	// 请参阅各个函数的文档
	// 了解每个函数在算法中的作用。
	numLMS := placeLMS_64(text, sa, freq, bucket)
	if numLMS <= 1 {
		// 0或1项已排序。什么也不做。
	} else {
		induceSubL_64(text, sa, freq, bucket)
		induceSubS_64(text, sa, freq, bucket)
		length_64(text, sa, numLMS)
		maxID := assignID_64(text, sa, numLMS)
		if maxID < numLMS {
			map_64(sa, numLMS)
			recurse_64(sa, tmp, numLMS, maxID)
			unmap_64(text, sa, numLMS)
		} else {
			// 如果maxID==numls，则每个LMS子字符串
			// 是唯一的，因此两个LMS后缀
			// 的相对顺序仅由前导的LMS子字符串确定。
			// 也就是说，LMS后缀排序顺序与
			// （更简单的）LMS子字符串排序顺序匹配。
			// 将原始LMS子字符串顺序复制到
			// 后缀数组目标中。
			copy(sa, sa[len(sa)-numLMS:])
		}
		expand_64(text, freq, bucket, sa, numLMS)
	}
	induceL_64(text, sa, freq, bucket)
	induceS_64(text, sa, freq, bucket)

	// 为呼叫者标记我们重写了tmp。
	tmp[0] = -1
}

func freq_8_64(text []byte, freq, bucket []int64) []int64 {
	if freq != nil && freq[0] >= 0 {
		return freq // 已计算
	}
	if freq == nil {
		freq = bucket
	}

	freq = freq[:256] // 消除
	for i := range freq {
		freq[i] = 0
	}
	for _, c := range text {
		freq[c]++
	}
	return freq
}

func freq_32(text []int32, freq, bucket []int32) []int32 {
	if freq != nil && freq[0] >= 0 {
		return freq // 已计算
	}
	if freq == nil {
		freq = bucket
	}

	for i := range freq {
		freq[i] = 0
	}
	for _, c := range text {
		freq[c]++
	}
	return freq
}

func freq_64(text []int64, freq, bucket []int64) []int64 {
	if freq != nil && freq[0] >= 0 {
		return freq // 已计算
	}
	if freq == nil {
		freq = bucket
	}

	for i := range freq {
		freq[i] = 0
	}
	for _, c := range text {
		freq[c]++
	}
	return freq
}

func bucketMin_8_64(text []byte, freq, bucket []int64) {
	freq = freq_8_64(text, freq, bucket)
	freq = freq[:256]     // 建立len（freq）=256，因此0≤ i<256低于
	bucket = bucket[:256] // 消除桶的边界检查[i]低于
	total := int64(0)
	for i, n := range freq {
		bucket[i] = total
		total += n
	}
}

func bucketMin_32(text []int32, freq, bucket []int32) {
	freq = freq_32(text, freq, bucket)
	total := int32(0)
	for i, n := range freq {
		bucket[i] = total
		total += n
	}
}

func bucketMin_64(text []int64, freq, bucket []int64) {
	freq = freq_64(text, freq, bucket)
	total := int64(0)
	for i, n := range freq {
		bucket[i] = total
		total += n
	}
}

func bucketMax_8_64(text []byte, freq, bucket []int64) {
	freq = freq_8_64(text, freq, bucket)
	freq = freq[:256]     // 建立len（freq）=256，因此0≤ 我在ABCDEG
	total := int64(0)
	for i, n := range freq {
		total += n
		bucket[i] = total
	}
}

func bucketMax_32(text []int32, freq, bucket []int32) {
	freq = freq_32(text, freq, bucket)
	total := int32(0)
	for i, n := range freq {
		total += n
		bucket[i] = total
	}
}

func bucketMax_64(text []int64, freq, bucket []int64) {
	freq = freq_64(text, freq, bucket)
	total := int64(0)
	for i, n := range freq {
		total += n
		bucket[i] = total
	}
}

func placeLMS_8_64(text []byte, sa, freq, bucket []int64) int {
	bucketMax_8_64(text, freq, bucket)

	numLMS := 0
	lastB := int64(-1)

	// 也就是说，i+1是LMS子字符串的起始位置。
	// 这些可以通过回调提升到函数中，
	// 但速度成本很高。相反，我们只是在这个源文件中写了几行
	// 代码。下面的副本
	// 引用此原件建立的模式，即
	// “LMS子字符串迭代器”。
	// 
	// 在每次扫描文本时，c0、c1是文本的连续字符。
	// 在这个反向扫描中，c0==text[i]和c1==text[i+1]。
	// 通过向后扫描，我们可以跟踪当前
	// 位置是S型还是L型，根据通常的定义：
	// 
	// /-位置len（text）是S型，带有文本[len（text）]=-1（哨兵）
	// /-位置i是S型，如果文本[i]<text[i+1]，或者如果text[i]==text[i+1]和&i+1是类型S。如果text[i]>text[i+1]，或者如果text[i]==text[i+1]和&i+1是类型L，则位置i是类型L。如果text[i]==text[i+1]和&i+1是类型L，则位置i是类型。
	// 反向扫描允许我们维护当前类型，
	// 当我们看到c0=c1，否则别管它。
	// 我们想用前面的L来标识所有的S位置。
	// 位置len（text）根据定义就是这样一个位置，但是我们没有地方写它，所以我们通过在循环开始时不正确地设置isTypeS=false来消除它。
	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 为LMS子字符串的开始设置索引i+1。
			b := bucket[c1] - 1
			bucket[c1] = b
			sa[b] = int64(i + 1)
			lastB = b
			numLMS++
		}
	}

	// 我们记录了LMS子字符串的开始，但确实想要结束。
	// 幸运的是，有两个不同之处，开始索引和结束索引是相同的。
	// 第一个区别是最右边的LMS子字符串的结束索引是len（text），
	// 因此调用者必须假装sa[-1]==len（text），如上所述。
	// 第二个区别是，第一个最左边的LMS子字符串开始索引
	// 没有结束较早的LMS子字符串，因此作为优化，我们可以省略
	// 最左边的LMS子字符串开始索引（我们编写的最后一个）。
	// 
	// 异常：如果numls<=1，调用方根本不需要处理
	// 递归，并且会将结果视为包含LMS子字符串。
	// 在这种情况下，我们不会删除最终条目。ABCFDG＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊。
	if numLMS > 1 {
		sa[lastB] = 0
	}
	return numLMS
}

func placeLMS_32(text []int32, sa, freq, bucket []int32) int {
	bucketMax_32(text, freq, bucket)

	numLMS := 0
	lastB := int32(-1)

	// 也就是说，i+1是LMS子串的开始位置。
	// 可以通过回调将它们提升到一个函数中，
	// 但是速度代价很大。相反，我们只是在这个源文件中写了几行
	// 代码。下面的副本
	// 引用了由该原件建立的模式，即
	// “LMS子字符串迭代器”。
	// 
	// 每次扫描文本时，c0、c1是文本的连续字符。
	// 在这个反向扫描中，c0==text[i]和c1==text[i+1]。
	// 通过向后扫描，我们可以跟踪当前
	// 位置是S型还是L型，根据通常的定义：
	// 
	// /-位置len（text）是S型，带有文本[len（text）]=-1（哨兵）
	// /-位置i是S型，如果文本[i]<text[i+1]，或者如果text[i]==text[i+1]&&i+1是类型S。如果text[i]>text[i+1]，或者如果text[i]==text[i+1]&&i+1是类型L，则位置i是类型L。如果text[i]==text[i+1]&&i+1是类型S，则位置i是类型。如果text[i]==text[i]=text[i+1]&&i+1]是类型L，则位置i是位置i。如果text[i]==text[i]==text[i+1]是类型S，则位置i+1是类型S。
	// 我们想用前面的L来标识所有的S位置。
	// 位置len（text）根据定义就是这样一个位置，但是我们没有地方写它，所以我们通过在循环开始时不正确地设置isTypeS=false来消除它。
	c0, c1, isTypeS := int32(0), int32(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// Bucket索引i+1用于LMS子字符串的开始。
			b := bucket[c1] - 1
			bucket[c1] = b
			sa[b] = int32(i + 1)
			lastB = b
			numLMS++
		}
	}

	// 我们记录了LMS子字符串的开始，但确实想要结束。
	// 幸运的是，有两个不同之处，开始索引和结束索引是相同的。
	// 第一个区别是最右边的LMS子字符串的结束索引是len（text），
	// 因此调用者必须假装sa[-1]==len（text），如上所述。
	// 第二个区别是最左边的第一个LMS子字符串开始索引
	// 不结束较早的LMS子字符串，因此作为优化，我们可以省略
	// 最左边的LMS子字符串开始索引（我们编写的最后一个）。
	// 
	// 异常：如果numls<=1，调用方根本不需要处理
	// 递归，并将结果视为包含LMS子字符串。
	// 在这种情况下，我们不会删除最终条目。ABCFDG＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊。
	if numLMS > 1 {
		sa[lastB] = 0
	}
	return numLMS
}

func placeLMS_64(text []int64, sa, freq, bucket []int64) int {
	bucketMax_64(text, freq, bucket)

	numLMS := 0
	lastB := int64(-1)

	// 也就是说，i+1是LMS子串的开始位置。
	// 可以通过回调将它们提升到一个函数中，但速度代价很大。相反，我们只是在这个源文件中写了几行
	// 代码。下面的副本
	// 引用此原件建立的模式，即
	// “LMS子字符串迭代器”。
	// 
	// 在每次扫描文本时，c0、c1是文本的连续字符。
	// 在这个反向扫描中，c0==text[i]和c1==text[i+1]。
	// 通过向后扫描，我们可以跟踪当前
	// 位置是S型还是L型，根据通常的定义：
	// 
	// /-位置len（text）是S型，带有文本[len（text）]=-1（哨兵）
	// /-位置i是S型，如果文本[i]<text[i+1]，或者如果text[i]==text[i+1]和&i+1是类型S。如果text[i]>text[i+1]，或者如果text[i]==text[i+1]和&i+1是类型L，则位置i是类型L。如果text[i]==text[i+1]和&i+1是类型L，则位置i是类型。如果text[i]==text[i+1]和&i+1是类型L，则位置i是类型。
	// 我们想用前面的L来标识所有的S位置。
	// 位置len（text）就是这样一个位置，但是我们没有地方写它，所以我们通过在循环开始时不正确地设置isTypeS=false来消除它。
	c0, c1, isTypeS := int64(0), int64(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// Bucket索引i+1用于LMS子字符串的开始。
			b := bucket[c1] - 1
			bucket[c1] = b
			sa[b] = int64(i + 1)
			lastB = b
			numLMS++
		}
	}

	// 我们记录了LMS子字符串的开始，但确实想要结束。
	// 幸运的是，有两个不同之处，开始索引和结束索引是相同的。
	// 第一个区别是最右边的LMS子字符串的结束索引是len（text），
	// 因此调用者必须假装sa[-1]==len（text），如上所述。
	// 第二个区别是，第一个最左边的LMS子字符串开始索引
	// 没有结束前面的LMS子字符串，因此作为优化，我们可以省略最左边的LMS子字符串开始索引（我们编写的最后一个）。
	// 
	// 异常：如果numls<=1，调用方根本不需要处理
	// 递归，并且会将结果视为包含LMS子字符串。
	// 在这种情况下，我们不会删除最终条目。
	if numLMS > 1 {
		sa[lastB] = 0
	}
	return numLMS
}

func induceSubL_8_64(text []byte, sa, freq, bucket []int64) {
	// 初始化字符桶左侧的位置。
	bucketMin_8_64(text, freq, bucket)
	bucket = bucket[:256] // 取消对

	// 下面的bucket[cB]的边界检查
	// 当我们从左到右扫描数组时，每个sa[i]=j>0都是一个正确的
	// 排序的后缀数组项（对于文本[j:]），我们知道j-1是L类型。
	// 因为j-1是L类型，现在将其插入sa将正确排序。
	// 但是我们想要区分类型为L和类型为S的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果前面有类型S，我们通过对j-1求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i´>i在sa[i´发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递将以排序但不一定相邻的顺序看到索引j、j-1、j-2、j-3、
	// 等等，直到它发现
	// 前面有一个类型为S的索引，此时它必须停止。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 然后将sa[i]<0翻转为-sa[i]，这样循环结束时，sa包含
	// 每个LMS子字符串的最左侧L型索引的索引。
	// 
	// 因此，后缀数组sa同时用作输入、输出和
	// 还有一个精心定制的工作队列。

	// placeLMS_8_64遗漏了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket index:
	// 我们正在按排序顺序处理后缀
	// 并访问排序顺序前由
	// 字节索引的bucket，这仍然是
	// 具有很好的局部性。
	// 不变量：b已缓存，可能是bucket[cB]的脏副本。
	cB := c1
	b := bucket[cB]
	sa[b] = int64(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		if j < 0 {
			// 为调用者保留发现的S型索引。
			sa[i] = int64(-j)
			continue
		}
		sa[i] = 0

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则队列-k为调用者保存。
		k := j - 1
		c0, c1 := text[k-1], text[k]
		if c0 < c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int64(k)
		b++
	}
}

func induceSubL_32(text []int32, sa, freq, bucket []int32) {
	// 初始化字符桶左侧的位置。
	bucketMin_32(text, freq, bucket)

	// 当我们从左到右扫描数组时，每个sa[i]=j>0都是正确的
	// 排序后缀数组条目（对于文本[j:]），我们知道j-1是L类型。
	// 因为j-1是L类型，现在将其插入sa将正确排序。
	// 但是我们想区分类型为L和类型为S的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果前面有类型S，我们通过对j-1求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i´>i在sa[i´发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递将以排序但不一定相邻的顺序看到索引j、j-1、j-2、j-3、
	// 等等，直到它找到
	// 一个前面有一个S类型索引的索引，此时它必须停止。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 并将sa[i]<0翻转为-sa[i]，这样循环结束时，sa包含
	// 每个LMS子字符串的最左侧L型索引的索引。
	// 
	// 因此，后缀数组sa同时充当输入、输出、
	// 和一个精心定制的工作队列。

	// placelms32遗漏了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa正确从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket index:
	// 我们正在按排序顺序处理后缀
	// 并访问排序顺序前由
	// int32索引的bucket，这仍然是
	// 具有很好的局部性。
	// 不变量：b已缓存，可能是bucket[cB]的脏副本。
	cB := c1
	b := bucket[cB]
	sa[b] = int32(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		if j < 0 {
			// 为调用者保留发现的S型索引。
			sa[i] = int32(-j)
			continue
		}
		sa[i] = 0

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则队列-k为调用者保存。
		k := j - 1
		c0, c1 := text[k-1], text[k]
		if c0 < c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int32(k)
		b++
	}
}

func induceSubL_64(text []int64, sa, freq, bucket []int64) {
	// 初始化字符桶左侧的位置。
	bucketMin_64(text, freq, bucket)

	// 当我们从左到右扫描数组时，每个sa[i]=j>0都是正确的
	// 排序后缀数组条目（对于文本[j:]），我们知道j-1是L类型。
	// 因为j-1是L类型，现在将其插入sa将正确排序。
	// 但是我们想要区分类型为L和类型为S的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果前面有类型S，我们通过对j-1求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i´>i在sa[i´发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递将以排序但不一定相邻的顺序看到索引j、j-1、j-2、j-3、
	// 等等，直到它发现
	// 前面有一个类型为S的索引，此时它必须停止。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 我们将sa[i]<0翻转为-sa[i]，这样循环结束时，sa包含
	// 对于每个LMS子字符串，只包含最左边的L型索引的索引。
	// 
	// 因此，后缀数组sa同时充当输入、输出、
	// 和一个精心定制的工作队列。

	// placeLMS_64遗漏了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa正确从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket index:
	// 我们正在按排序顺序处理后缀
	// 并访问排序顺序前由
	// int64索引的bucket，这仍然是
	// 具有很好的局部性。
	// 不变量：b已缓存，可能是bucket[cB]的脏副本。
	cB := c1
	b := bucket[cB]
	sa[b] = int64(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		if j < 0 {
			// 为调用者保留发现的S型索引。
			sa[i] = int64(-j)
			continue
		}
		sa[i] = 0

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则队列-k为调用者保存。
		k := j - 1
		c0, c1 := text[k-1], text[k]
		if c0 < c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int64(k)
		b++
	}
}

func induceSubS_8_64(text []byte, sa, freq, bucket []int64) {
	// 初始化字符桶右侧的位置。
	bucketMax_8_64(text, freq, bucket)
	bucket = bucket[:256] // 消除下面bucket[cB]的边界检查

	// 类似于上面的induceSubL_8_64，
	// 当我们从右向左扫描数组时，每个sa[i]=j>0都是正确的
	// 排序的后缀数组项（对于文本[j:]）我们知道j-1是S类型。
	// 因为j-1是S类型，现在将其插入sa将正确排序。
	// 但是我们想区分类型为S和类型为L的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果在j-1前面加上类型L，我们通过对其求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i´<i在sa[i´发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递将以排序但不一定相邻的顺序看到索引j、j-1、j-2、j-3、
	// 等等，直到它找到
	// 一个前面有L类型索引的索引，此时它必须停止。
	// 该索引（前面有一个类型为L的索引）是LMS子字符串的开始。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 然后将sa[i]<0翻转为-sa[i]，并压缩到sa的顶部，
	// 这样循环结束时sa的顶部正好包含
	// LMS子字符串开始索引，按LMS子字符串排序。

	// 缓存最近使用的bucket索引：
	cB := byte(0)
	b := bucket[cB]

	top := len(sa)
	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		sa[i] = 0
		if j < 0 {
			// 为调用者保留发现的LMS子字符串开始索引。
			top--
			sa[top] = int64(-j)
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是S型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将-k队列保存给调用者。
		k := j - 1
		c1 := text[k]
		c0 := text[k-1]
		if c0 > c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int64(k)
	}
}

func induceSubS_32(text []int32, sa, freq, bucket []int32) {
	// 初始化字符桶右侧的位置。
	bucketMax_32(text, freq, bucket)

	// 类似于上面的inquiredSubl_32，
	// 当我们从右向左扫描数组时，每个sa[i]=j>0都是一个正确的
	// 排序后缀数组条目（对于文本[j:]），我们知道j-1是S类型。
	// 因为j-1是S类型，现在将其插入sa将正确排序。
	// 但是我们想区分类型为S和类型为L的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果在j-1前面加上类型L，我们通过对其求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证在sa[i´´处发生，对于某些i´<i，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递将以排序但不一定相邻的顺序看到索引j、j-1、j-2、j-3、
	// 等等，直到它找到
	// 一个前面有L类型索引的索引，此时它必须停止。
	// 该索引（前面有一个类型为L的索引）是LMS子字符串的开始。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 我们将sa[i]<0翻转到-sa[i]并压缩到sa的顶部，
	// 这样循环结束时，sa的顶部正好包含
	// LMS子字符串开始索引，按LMS子字符串排序。

	// 缓存最近使用的bucket索引：
	cB := int32(0)
	b := bucket[cB]

	top := len(sa)
	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		sa[i] = 0
		if j < 0 {
			// 为调用者保留发现的LMS子字符串开始索引。
			top--
			sa[top] = int32(-j)
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是S型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将-k队列保存给调用者。
		k := j - 1
		c1 := text[k]
		c0 := text[k-1]
		if c0 > c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int32(k)
	}
}

func induceSubS_64(text []int64, sa, freq, bucket []int64) {
	// 初始化字符桶右侧的位置。
	bucketMax_64(text, freq, bucket)

	// 类似于上面的inquiredSubl_64，
	// 当我们从右向左扫描数组时，每个sa[i]=j>0都是一个正确的
	// 排序后缀数组条目（对于文本[j:]），我们知道j-1是S类型。
	// 因为j-1是S类型，现在将其插入sa将正确排序。
	// 但是我们想区分类型为S和类型为L的j-1和j-2。
	// 我们可以处理前者，但希望将后者留给调用方。
	// 如果在j-1前面加上类型L，我们通过对其求反来记录差异。
	// 无论哪种方式，插入（到文本[j-1]bucket中）都保证对某些i´<i在sa[i´发生，也就是说，在sa的部分，我们还有
	// 要扫描。因此，单次传递将以排序但不一定相邻的顺序看到索引j、j-1、j-2、j-3、
	// 等等，直到它找到
	// 一个前面有类型为L的索引，此时它必须停止。
	// 该索引（前面有一个类型为L的索引）是LMS子字符串的开始。
	// 
	// 当我们扫描数组时，我们将工作项（sa[i]>0）清除为零，
	// 然后将sa[i]<0翻转为-sa[i]，并压缩到sa的顶部，
	// 这样循环结束时，sa的顶部正好包含
	// LMS子字符串开始索引，按LMS子字符串排序。

	// 缓存最近使用的bucket索引：
	cB := int64(0)
	b := bucket[cB]

	top := len(sa)
	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j == 0 {
			// 跳过空条目。
			continue
		}
		sa[i] = 0
		if j < 0 {
			// 为调用者保留发现的LMS子字符串开始索引。
			top--
			sa[top] = int64(-j)
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是S型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，请将k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将-k队列保存给调用者。
		k := j - 1
		c1 := text[k]
		c0 := text[k-1]
		if c0 > c1 {
			k = -k
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int64(k)
	}
}

func length_8_64(text []byte, sa []int64, numLMS int) {
	end := 0 // 当前LMS子字符串结束的索引（0表示最终的LMS子字符串）

	// 将N个文本字节编码为一个“长度”字
	// 每个字节加1，并将其打包到字的底部
	// N*8位，然后按位反转结果。
	// 也就是说，文本序列A B C（十六进制41 42 43）
	// 编码为^uint64（0x42_43_44）。
	// LMS子字符串不能以0xFF开头或结尾。
	// 添加1确保编码的字节序列不会以0x00开始或结束，因此当前字节可以是
	// 区别于顶部位的零填充，
	// 因此长度不需要单独编码。
	// 反转字节会增加仍然使用
	// 4字节编码的可能性≥ len（文本）。
	// 特别是，如果第一个字节是ASCII（<=0x7E，so+1<=0x7F）
	// 那么将设置反转的高位，
	// 使其明显不是有效长度（它将是负长度）。
	// 
	// cx保存预反转编码（压缩递增字节）。ABCFDG＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊64中，已描述了一个行，以维持CX。

	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		cx = cx<<8 | uint64(c1+1) // 仅字节
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 索引j=i+1是LMS子字符串的开始。
			// 计算要存储在sa中的长度或编码文本[j/2]。
			j := i + 1
			var code int64
			if end == 0 {
				code = 0
			} else {
				code = int64(end - j)
				if code <= 64/8 && ^cx >= uint64(len(text)) { // 仅字节
					code = int64(^cx) // 仅字节
				} // 仅字节
			}
			sa[j>>1] = code
			end = j + 1
			cx = uint64(c1 + 1) // 仅字节
		}
	}
}

func length_32(text []int32, sa []int32, numLMS int) {
	end := 0 // 当前LMS子字符串结束的索引（0表示最终LMS子字符串）

	// 将N个文本int32s编码为“长度”字
	// 在每个int32中添加1，将它们打包到字的底部
	// N*8位，然后按位反转结果。
	// 即文本序列A B C（十六进制41 42 43）
	// 编码为^uint32（0x42\u 43\u 44）。
	// LMS子字符串不能以0xFF开头或结尾。
	// 添加1确保编码的int32序列永远不会以0x00开始或结束，因此当前的int32可以是
	// 区别于顶部位的零填充，
	// 因此长度不需要单独编码。
	// 反转int32s会增加
	// 4-int32编码仍然有效的可能性≥ len（文本）。
	// 特别是，如果第一个int32是ASCII（<=0x7E，so+1<=0x7F）
	// 则将设置反转的高位，
	// 使其显然不是有效长度（它将是负长度）。
	// 
	// cx保存预反转编码（压缩递增int32s）。ABCFDG 

	c0, c1, isTypeS := int32(0), int32(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 索引j=i+1是LMS子字符串的开始。
			// 计算要存储在sa中的长度或编码文本[j/2]。
			j := i + 1
			var code int32
			if end == 0 {
				code = 0
			} else {
				code = int32(end - j)
			}
			sa[j>>1] = code
			end = j + 1
		}
	}
}

func length_64(text []int64, sa []int64, numLMS int) {
	end := 0 // 当前LMS子串结束的索引（0表示最终的LMS子串）

	// 将N个文本int64s编码为一个“长度”字
	// 将每个int64加1，将它们打包到字的底部
	// N*8位，然后按位反转结果。
	// 也就是说，文本序列A B C（十六进制41 42 43）
	// 编码为^uint64（0x42_43_44）。
	// LMS子字符串不能以0xFF开头或结尾。
	// 添加1确保编码的int64序列不会以0x00开始或结束，因此当前int64可以是
	// 区别于顶部位的零填充，
	// 因此长度不需要单独编码。
	// 反转int64s会增加仍然使用
	// 4-int64编码的可能性≥ len（文本）。
	// 特别是，如果第一个int64是ASCII（<=0x7E，so+1<=0x7F）
	// 则将设置反转的高位，
	// 使其显然不是有效长度（它将是负长度）。
	// 
	// cx保存预反转编码（压缩递增int64s）。ABCFDG 

	c0, c1, isTypeS := int64(0), int64(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 索引j=i+1是LMS子字符串的开始。
			// 计算要存储在sa中的长度或编码文本[j/2]。
			j := i + 1
			var code int64
			if end == 0 {
				code = 0
			} else {
				code = int64(end - j)
			}
			sa[j>>1] = code
			end = j + 1
		}
	}
}

func assignID_8_64(text []byte, sa []int64, numLMS int) int {
	id := 0
	lastLen := int64(-1) // 不可能
	lastPos := int64(0)
	for _, j := range sa[len(sa)-numLMS:] {
		// 索引j处的LMS子字符串是新的，还是与我们上次看到的相同？
		n := sa[j/2]
		if n != lastLen {
			goto New
		}
		if uint64(n) >= uint64(len(text)) {
			// /“长度”实际上是编码的全文，并且它们匹配。
			goto Same
		}
		{
			// 比较实际文本。
			n := int(n)
			this := text[j:][:n]
			last := text[lastPos:][:n]
			for i := 0; i < n; i++ {
				if this[i] != last[i] {
					goto New
				}
			}
			goto Same
		}
	New:
		id++
		lastPos = j
		lastLen = n
	Same:
		sa[j/2] = int64(id)
	}
	return id
}

func assignID_32(text []int32, sa []int32, numLMS int) int {
	id := 0
	lastLen := int32(-1) // 不可能
	lastPos := int32(0)
	for _, j := range sa[len(sa)-numLMS:] {
		// 索引j处的LMS子字符串是新的，还是与我们上次看到的相同？
		n := sa[j/2]
		if n != lastLen {
			goto New
		}
		if uint32(n) >= uint32(len(text)) {
			// /“长度”实际上是全文编码的，并且它们匹配。
			goto Same
		}
		{
			// 比较实际文本。
			n := int(n)
			this := text[j:][:n]
			last := text[lastPos:][:n]
			for i := 0; i < n; i++ {
				if this[i] != last[i] {
					goto New
				}
			}
			goto Same
		}
	New:
		id++
		lastPos = j
		lastLen = n
	Same:
		sa[j/2] = int32(id)
	}
	return id
}

func assignID_64(text []int64, sa []int64, numLMS int) int {
	id := 0
	lastLen := int64(-1) // 不可能
	lastPos := int64(0)
	for _, j := range sa[len(sa)-numLMS:] {
		// 索引j处的LMS子字符串是新的，还是与我们上次看到的相同？
		n := sa[j/2]
		if n != lastLen {
			goto New
		}
		if uint64(n) >= uint64(len(text)) {
			// /“长度”实际上是全文编码的，并且它们匹配。
			goto Same
		}
		{
			// 比较实际文本。
			n := int(n)
			this := text[j:][:n]
			last := text[lastPos:][:n]
			for i := 0; i < n; i++ {
				if this[i] != last[i] {
					goto New
				}
			}
			goto Same
		}
	New:
		id++
		lastPos = j
		lastLen = n
	Same:
		sa[j/2] = int64(id)
	}
	return id
}

func map_64(sa []int64, numLMS int) {
	w := len(sa)
	for i := len(sa) / 2; i >= 0; i-- {
		j := sa[i]
		if j > 0 {
			w--
			sa[w] = j - 1
		}
	}
}

func recurse_64(sa, oldTmp []int64, numLMS, maxID int) {
	dst, saTmp, text := sa[:numLMS], sa[numLMS:len(sa)-numLMS], sa[len(sa)-numLMS:]

	// 为递归调用设置临时空间。
	// 我们必须向sais_64传递至少包含maxID项的tmp缓冲区。
	// 
	// 保证子问题的长度不超过len（sa）/2，
	// 以便sa可以同时容纳子问题及其后缀数组。
	// 但是，几乎所有的时候，子问题的长度都小于len（sa）/3，
	// 在这种情况下，有一个子问题大小在sa中间，
	// 我们可以重用为临时空间（saTmp）。
	// 当从sais_8_64调用recurse_64时，oldTmp的长度为512 
	// （从text_64），saTmp通常会大得多，因此我们将使用saTmp。
	// 当更深的递归返回到recurse_64时，现在oldTmp是
	// 从最上面的递归开始的saTmp，它通常比
	// 当前的saTmp大（因为当前sa随着递归的加深而变得越来越小），我们一直在重复使用最顶级的
	// 大型saTmp，而不是提供的小型saTmp。
	// 
	// 为什么子问题的长度经常小于len（sa）/3？
	// 有关合理的解释，请参见农、张和陈，第3.6节。
	// 简言之，len（sa）/2案例将对应于输入中的SLSL模式
	// 大小输入字节的完美交替。
	// Real text不会这样做。如果每个L-type索引后面随机跟随一个L-type或S-type索引，则一半子字符串的形式为SLS，但另一半较长。其中，
	// 一半（总的四分之一）将是SLL；第八个是SLLL，以此类推。
	// 不计算每一个中的最后一个S（与下一个中的第一个S重叠），
	// 计算出的平均长度为2×½+3×¼+4×2⅛ + ... = 3.
	// 我们需要的空间进一步减少了，因为许多像SLS这样的短模式通常都是相同的字符序列
	// 在整个文本中重复，从而减少了相对于numls的maxID。
	// 
	// 对于短输入，平均值可能不利于我们，但我们
	// 通常可以使用
	// 最顶端调用中可用的长度为512的tmp。（同样，短分配也不是什么大问题。）对于病理输入，我们返回到分配长度为
	// max（maxID，numls/2）的新tmp。这一级别的递归需要maxID，
	// 而所有更深层次的递归只需要numms/2，
	// 所以这一个分配保证足以满足整个堆栈
	// 的递归调用。
	tmp := oldTmp
	if len(tmp) < len(saTmp) {
		tmp = saTmp
	}
	if len(tmp) < numLMS {
		// TestSAIS/forcealloc到达此代码。
		n := maxID
		if n < numLMS/2 {
			n = numLMS / 2
		}
		tmp = make([]int64, n)
	}

	// sais_64要求调用者安排清除dst，
	// 因为通常调用者可能知道dst是
	// 新分配且已清除。但这个不是。
	for i := range dst {
		dst[i] = 0
	}
	sais_64(text, maxID, dst, tmp)
}

func unmap_8_64(text []byte, sa []int64, numLMS int) {
	unmap := sa[len(sa)-numLMS:]
	j := len(unmap)

	// /“LMS子串迭代器”（见上文placeLMS_8_64）。
	c0, c1, isTypeS := byte(0), byte(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 填充反向映射。
			j--
			unmap[j] = int64(i + 1)
		}
	}

	// 对子问题后缀数组应用逆映射。
	sa = sa[:numLMS]
	for i := 0; i < len(sa); i++ {
		sa[i] = unmap[sa[i]]
	}
}

func unmap_32(text []int32, sa []int32, numLMS int) {
	unmap := sa[len(sa)-numLMS:]
	j := len(unmap)

	// /“LMS子字符串迭代器”（见上文placeLMS_32）。
	c0, c1, isTypeS := int32(0), int32(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 填充逆映射。
			j--
			unmap[j] = int32(i + 1)
		}
	}

	// 对子问题后缀数组应用逆映射。
	sa = sa[:numLMS]
	for i := 0; i < len(sa); i++ {
		sa[i] = unmap[sa[i]]
	}
}

func unmap_64(text []int64, sa []int64, numLMS int) {
	unmap := sa[len(sa)-numLMS:]
	j := len(unmap)

	// /“LMS子字符串迭代器”（见上文placeLMS_64）。
	c0, c1, isTypeS := int64(0), int64(0), false
	for i := len(text) - 1; i >= 0; i-- {
		c0, c1 = text[i], c0
		if c0 < c1 {
			isTypeS = true
		} else if c0 > c1 && isTypeS {
			isTypeS = false

			// 填充逆映射。
			j--
			unmap[j] = int64(i + 1)
		}
	}

	// 对子问题后缀数组应用逆映射。
	sa = sa[:numLMS]
	for i := 0; i < len(sa); i++ {
		sa[i] = unmap[sa[i]]
	}
}

func expand_8_64(text []byte, freq, bucket, sa []int64, numLMS int) {
	bucketMax_8_64(text, freq, bucket)
	bucket = bucket[:256] // 消除对

	// 下面的bucket[c]的绑定检查，通过sa向后循环，始终跟踪
	// 从sa填充的下一个索引[：numls]。
	// 当我们找到一个时，填充它。
	// 将剩余插槽归零；他们有死的价值。
	x := numLMS - 1
	saX := sa[x]
	c := text[saX]
	b := bucket[c] - 1
	bucket[c] = b

	for i := len(sa) - 1; i >= 0; i-- {
		if i != int(b) {
			sa[i] = 0
			continue
		}
		sa[i] = saX

		// 加载下一个要放下的条目（如果有）。
		if x > 0 {
			x--
			saX = sa[x] // TODO边界检查
			c = text[saX]
			b = bucket[c] - 1
			bucket[c] = b
		}
	}
}

func expand_32(text []int32, freq, bucket, sa []int32, numLMS int) {
	bucketMax_32(text, freq, bucket)

	// 通过sa向后循环，始终跟踪
	// 从sa填充的下一个索引[：numls]。
	// 当我们找到一个时，填充它。
	// 将剩余插槽归零；他们有死的价值。
	x := numLMS - 1
	saX := sa[x]
	c := text[saX]
	b := bucket[c] - 1
	bucket[c] = b

	for i := len(sa) - 1; i >= 0; i-- {
		if i != int(b) {
			sa[i] = 0
			continue
		}
		sa[i] = saX

		// 加载下一个要放下的条目（如果有）。
		if x > 0 {
			x--
			saX = sa[x] // TODO边界检查
			c = text[saX]
			b = bucket[c] - 1
			bucket[c] = b
		}
	}
}

func expand_64(text []int64, freq, bucket, sa []int64, numLMS int) {
	bucketMax_64(text, freq, bucket)

	// 通过sa向后循环，始终跟踪
	// 从sa填充的下一个索引[：numls]。
	// 当我们找到一个时，填充它。
	// 将剩余插槽归零；他们有死的价值。
	x := numLMS - 1
	saX := sa[x]
	c := text[saX]
	b := bucket[c] - 1
	bucket[c] = b

	for i := len(sa) - 1; i >= 0; i-- {
		if i != int(b) {
			sa[i] = 0
			continue
		}
		sa[i] = saX

		// 加载下一个要放下的条目（如果有）。
		if x > 0 {
			x--
			saX = sa[x] // TODO边界检查
			c = text[saX]
			b = bucket[c] - 1
			bucket[c] = b
		}
	}
}

func induceL_8_64(text []byte, sa, freq, bucket []int64) {
	// 初始化字符桶左侧的位置。
	bucketMin_8_64(text, freq, bucket)
	bucket = bucket[:256] // 消除桶[cB]的边界检查

	// 此扫描与上面的INDUCTSUBL_8_64中的扫描类似。
	// 除最左边的L型索引外，安排清除所有索引。
	// 此扫描将保留所有L型索引和原始S型
	// 索引，但它将否定最左边的正L型索引
	// （导致_8_64的索引需要处理）。

	// expand_8_64省略了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa正确从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket索引。
	cB := c1
	b := bucket[cB]
	sa[b] = int64(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j <= 0 {
			// 跳过空的或否定的条目（包括否定的零）。
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则队列-k为调用者保存。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用方
		// 即可。调用方无法区分
		// 空插槽和非空零之间的区别，但无论如何也不需要
		// 来区分它们：最终的后缀数组将以
		// 结尾，在某个地方有一个零，这将是一个真正的零。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 < c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int64(k)
		b++
	}
}

func induceL_32(text []int32, sa, freq, bucket []int32) {
	// 初始化字符桶左侧的位置。
	bucketMin_32(text, freq, bucket)

	// 此扫描与上面第32页中的扫描类似。
	// 除最左边的L型索引外，安排清除所有索引。
	// 此扫描将保留所有L型索引和原始S型
	// 索引，但它将否定最左边的正L型索引
	// （导致_32的索引需要处理）。

	// expand_32省略了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket索引。
	cB := c1
	b := bucket[cB]
	sa[b] = int32(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j <= 0 {
			// 跳过空的或否定的条目（包括否定的零）。
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则队列-k为调用者保存。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用方
		// 即可。调用方无法区分
		// 空插槽和非空零之间的区别，但无论如何也不需要
		// 来区分它们：最终的后缀数组将以
		// 结尾，在某个地方有一个零，这将是一个真正的零。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 < c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int32(k)
		b++
	}
}

func induceL_64(text []int64, sa, freq, bucket []int64) {
	// 初始化字符桶左侧的位置。
	bucketMin_64(text, freq, bucket)

	// 此扫描与上面第64页中的扫描类似。
	// 除最左边的L型索引外，安排清除所有索引。
	// 此扫描将保留所有L型索引和原始S型
	// 索引，但它将否定最左侧的正L型索引
	// （导致_64的索引需要处理）。

	// expand_64遗漏了隐式条目sa[-1]==len（text），
	// 对应于标识的type-L索引len（text）-1。
	// 在sa从左向右扫描之前进行处理。
	// 有关评论，请参见循环正文。
	k := len(text) - 1
	c0, c1 := text[k-1], text[k]
	if c0 < c1 {
		k = -k
	}

	// 缓存最近使用的bucket索引。
	cB := c1
	b := bucket[cB]
	sa[b] = int64(k)
	b++

	for i := 0; i < len(sa); i++ {
		j := int(sa[i])
		if j <= 0 {
			// 跳过空的或否定的条目（包括否定的零）。
			continue
		}

		// 索引j在工作队列上，这意味着k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是L-type，则将k排队，以便稍后在此循环中处理。
		// 如果k-1是S-type（text[k-1]<text[k]），则队列-k为调用者保存。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用方
		// 即可。调用方无法区分
		// 空插槽和非空零之间的区别，但无论如何也不需要
		// 来区分它们：最终的后缀数组将以
		// 结尾，在某个地方有一个零，这将是一个真正的零。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 < c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		sa[b] = int64(k)
		b++
	}
}

func induceS_8_64(text []byte, sa, freq, bucket []int64) {
	// 初始化字符桶右侧的位置。
	bucketMax_8_64(text, freq, bucket)
	bucket = bucket[:256] // 消除桶[cB]在

	cB := byte(0)
	b := bucket[cB]

	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j >= 0 {
			// 下面的边界检查跳过未标记的条目。
			// （此循环无法看到空条目；0表示实际零索引。）
			continue
		}

		// /负j是工作队列条目；将最终后缀数组重写为正j。
		j = -j
		sa[i] = int64(j)

		// 索引j在工作队列上（编码为-j，但现在已解码），
		// 意思是k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，则将-k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将k排队以保存给调用方。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用者
		// 即可。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 <= c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int64(k)
	}
}

func induceS_32(text []int32, sa, freq, bucket []int32) {
	// 初始化字符桶右侧的位置。
	bucketMax_32(text, freq, bucket)

	cB := int32(0)
	b := bucket[cB]

	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j >= 0 {
			// 跳过未标记的条目。
			// （此循环无法看到空条目；0表示实际零索引。）
			continue
		}

		// /负j是工作队列条目；将最终后缀数组重写为正j。
		j = -j
		sa[i] = int32(j)

		// 索引j在工作队列上（编码为-j，但现在已解码），
		// 表示k:=j-1为L型，
		// 现在我们可以将k正确地放入sa中。
		// 如果k-1是S-type，则将-k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将k排队以保存给调用方。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用者
		// 即可。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 <= c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int32(k)
	}
}

func induceS_64(text []int64, sa, freq, bucket []int64) {
	// 初始化字符桶右侧的位置。
	bucketMax_64(text, freq, bucket)

	cB := int64(0)
	b := bucket[cB]

	for i := len(sa) - 1; i >= 0; i-- {
		j := int(sa[i])
		if j >= 0 {
			// 跳过未标记的条目。
			// （此循环无法看到空条目；0表示实际零索引。）
			continue
		}

		// /负j是工作队列条目；将最终后缀数组重写为正j。
		j = -j
		sa[i] = int64(j)

		// 索引j在工作队列上（编码为-j，但现在已解码），
		// 意思是k:=j-1是L型，
		// 因此我们现在可以将k正确地放入sa中。
		// 如果k-1是S-type，则将-k排队，以便稍后在此循环中处理。
		// 如果k-1是L-type（text[k-1]>text[k]），则将k排队以保存给调用方。
		// 如果k为零，则k-1不存在，因此我们只需将其留给调用者
		// 即可。
		k := j - 1
		c1 := text[k]
		if k > 0 {
			if c0 := text[k-1]; c0 <= c1 {
				k = -k
			}
		}

		if cB != c1 {
			bucket[cB] = b
			cB = c1
			b = bucket[cB]
		}
		b--
		sa[b] = int64(k)
	}
}
